package leetcode;

import leetcode.entity.ListNode;

/**
 * 思路：将lists 拆成两两合并。最后合并总的
 * @author:xufengxiang
 * @date 2023-04-11 19:16
 */
public class Code23 {

    //从头到尾两两合并
    public ListNode mergeKLists(ListNode[] lists) {
        int length = lists.length;
        if(length == 0){
            return null;
        }
        if(length == 1){
            return lists[0];
        }
        if(length == 2){
           return mergeList(lists[0],lists[1]);
        }

        ListNode head = lists[0];
        for(int i=1;i< length;i++){
            head = mergeList(head, lists[i]);
        }
        return head;
    }

    //分治两两合并
    public ListNode mergeKListDfs(ListNode[] lists){
        int length = lists.length;
        if(length == 0){
            return null;
        }
        if(length == 1){
            return lists[0];
        }
        if(length == 2){
            return mergeList(lists[0],lists[1]);
        }
        return mergeMid(lists,0,length-1);
    }

    public static ListNode mergeMid(ListNode[] lists, int left, int right){
        if(left >= right){
            return lists[left];
        }
        int mid = (right + left)/2;
        ListNode l = mergeMid(lists, left,mid);
        ListNode r = mergeMid(lists, mid+1, right);
        return mergeList(l, r);
    }

    public static ListNode mergeList(ListNode l1, ListNode l2){
        ListNode head = new ListNode();
        ListNode p = head;
        while( l1 != null && l2 != null){
            if(l1.val <= l2.val){
                p.next = l1;
                l1 = l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if(l1 == null){
            p.next = l2;
        }
        if(l2 == null){
            p.next = l1;
        }
        return head.next;
    }
}
